package datastructure.structure;


import java.util.Arrays;
import java.util.function.BiFunction;

/**
 * 线段树
 *
 * @author or2
 * @date 2021/8/8 20:04
 */
public class SegmentTree<E> {

    private E[] tree;
    private E[] data;
    private BiFunction<E, E, E> merge;

    /**
     * 构造线段树
     *
     * @param arr   原数组
     * @param merge 线段树合并方式
     */
    public SegmentTree(E[] arr, BiFunction<E, E, E> merge) {
        this.data = arr.clone();
        this.tree = (E[]) new Object[arr.length << 2];
        this.merge = merge;

        buildTree(0, 0, arr.length - 1);
    }

    /**
     * 递归->建立线段树
     *
     * @param treeIndex 当前结点索引
     * @param lp        范围的左边界
     * @param rp        范围的右边界
     */
    private void buildTree(int treeIndex, int lp, int rp) {
        if (lp == rp) {
            tree[treeIndex] = data[lp];
            return;
        }

        int leftChild = leftChild(treeIndex);
        int rightChild = rightChild(treeIndex);

        int mid = lp + (rp - lp >> 1);
        buildTree(leftChild, lp, mid);
        buildTree(rightChild, mid + 1, rp);

        tree[treeIndex] = merge.apply(tree[leftChild], tree[rightChild]);
    }

    /**
     * 查询线段树区间值
     *
     * @param lbound 查询左区间
     * @param rbound 查询右区间
     * @return 查询的结果
     */
    public E query(int lbound, int rbound) {

        if (lbound < 0 || rbound >= data.length || rbound < 0 || lbound > rbound) {
            throw new IllegalArgumentException("参数不合法!");
        }

        return query(0, 0, data.length - 1, lbound, rbound);
    }

    /**
     * 递归->从 {@code treeIndex} 标定的范围为 {@code [lRange, rRange] }的结点开始查找, <br/>
     * {@code lbound, rbound} 用来传递查找范围
     *
     * @param treeIndex 当前结点下标
     * @param lRange    当前结点所表示数值的 右边界
     * @param rRange    当前结点所表示数值的 左边界
     * @param lbound    查找区间的左边界
     * @param rbound    查找区间的右边界
     * @return 查找结果
     */
    private E query(int treeIndex, int lRange, int rRange, int lbound, int rbound) {
        if (lRange == lbound && rRange == rbound) {
            return tree[treeIndex];
        }

        int mid = lRange + (rRange - lRange >> 1);
        int leftChild = leftChild(treeIndex);
        int rightChild = rightChild(treeIndex);
        if (lbound >= mid + 1) {
            return query(rightChild, mid + 1, rRange, lbound, rbound);
        } else if (rbound <= mid) {
            return query(leftChild, lRange, mid, lbound, rbound);
        }

        return merge.apply(query(rightChild, mid + 1, rRange, mid + 1, rbound),
                query(leftChild, lRange, mid, lbound, mid));
    }

    /**
     * 将 下标为 {@code index} 的结点的值更新-> {@code value}
     * @param index 更新结点的下标
     * @param value 更新后的值
     */
    public void set(int index, E value) {
        set(0, 0, data.length - 1, index, value);
    }

    /**
     * 递归->先查找到索引{@code index} 所指🥥叶子结点, 向上上浮修改父节点
     * @param cIndex 当前结点索引
     * @param lRange 查找的左边界
     * @param rRange 当前查找的右边界
     * @param index 需要修改的结点的叶子索引
     * @param value 修改后的值
     */
    private void set(int cIndex, int lRange, int rRange, int index, E value) {

//        查找到🥥叶子结点后, 逐级修改父亲结点
        if (lRange == rRange) {
            tree[cIndex] = value;
            if (cIndex == 0) {
                return;
            }
            int parentIndex = cIndex - 1 >> 1;
            while (true) {
                int leftChild = leftChild(parentIndex);
                tree[parentIndex] = merge.apply(tree[leftChild], tree[leftChild + 1]);
                if (parentIndex == 0) {
                    return;
                }
                parentIndex = parentIndex - 1 >> 1;
            }
        }

//        递归->查找 索引所指🥥叶子结点
        int mid = lRange + (rRange - lRange >> 1);
        int leftChild = leftChild(cIndex);
        int rightChild = rightChild(cIndex);
        if (index >= mid + 1) {
            set(rightChild, mid + 1, rRange, index, value);
        } else {
            set(leftChild, lRange, mid, index, value);
        }
    }


    /**
     * 返回数据个数
     *
     * @return 数据数量
     */
    public int getSize() {
        return data.length;
    }

    /**
     * 返回该节点的左孩子结点的索引
     *
     * @param index 结点的索引
     * @return 左孩子的索引
     */
    private int leftChild(int index) {
        return (index << 1) + 1;
    }

    /**
     * 返回该节点的右孩子结点的索引
     *
     * @param index 结点的索引
     * @return 右孩子的索引
     */
    private int rightChild(int index) {
        return index + 1 << 1;
    }

    @Override
    public String toString() {
        return "SegmentTree{" +
                "tree=" + Arrays.toString(tree) +
                '}';
    }
}
